{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Squareful Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSquarefulPerms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #正方形数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非负整数数组&nbsp;<code>A</code>，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为<em>正方形</em>数组。</p>\n",
    "\n",
    "<p>返回 A 的正方形排列的数目。两个排列 <code>A1</code> 和 <code>A2</code> 不同的充要条件是存在某个索引 <code>i</code>，使得 A1[i] != A2[i]。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[1,17,8]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "[1,8,17] 和 [17,8,1] 都是有效的排列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[2,2,2]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= A.length &lt;= 12</code></li>\n",
    "\t<li><code>0 &lt;= A[i] &lt;= 1e9</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-squareful-arrays](https://leetcode.cn/problems/number-of-squareful-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-squareful-arrays](https://leetcode.cn/problems/number-of-squareful-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,17,8]', '[2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    回溯\n",
    "    使用 count 记录对于每一种值还有多少个节点等待被访问，与一个变量 todo 记录还剩多少个节点等待被访问。\n",
    "    对于每一个节点，我们可以访问它的所有邻居节点（从数值的角度来看，从而大大减少复杂度）。\n",
    "    对于每一个节点，我们可以访问它的所有邻居节点（从数值的角度来看，从而大大减少复杂度）。\n",
    "    '''\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = collections.Counter(nums)\n",
    "\n",
    "        graph = {x: [] for x in count}\n",
    "        for x in count:\n",
    "            for y in count:\n",
    "                if int((x+y)**.5 + 0.5) ** 2 == x+y:\n",
    "                    graph[x].append(y)\n",
    "\n",
    "        def dfs(x, todo: int) -> int:\n",
    "            count[x] -= 1\n",
    "            if todo == 0:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for y in graph[x]:\n",
    "                    if count[y]:\n",
    "                        ans += dfs(y, todo - 1)\n",
    "            count[x] += 1\n",
    "            return ans\n",
    "\n",
    "        return sum(dfs(x, n - 1) for x in count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        # 全排列，之后判断相邻元素之和是否是某个数的平方\n",
    "        # 1.降序后进行回溯\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        tmp = []\n",
    "        self.dfs(nums, res, tmp, 0)\n",
    "        return len(res)\n",
    "    def dfs(self, nums, res, tmp, prenum):\n",
    "        # 1.1 回溯的终止条件,最终tmp元素与nums元素一致，则OK\n",
    "        if len(tmp) == len(nums):\n",
    "            x = tmp[:]\n",
    "            x.sort()\n",
    "            if x == nums:\n",
    "                res.append(tmp)\n",
    "            return\n",
    "        # 1.2 单层递归的逻辑\n",
    "        for i in range(len(nums)):\n",
    "\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            if prenum > 0 and not self.isvalid(prenum + nums[i]):\n",
    "                continue\n",
    "            tmp.append(nums[i])\n",
    "            self.dfs(nums, res, tmp, nums[i])\n",
    "            tmp.pop()\n",
    "    def isvalid(self, n):\n",
    "        return n == int(n ** 0.5) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        u = (1 << n) - 1\n",
    "        def check(a: int, b: int) -> bool:\n",
    "            return sqrt(a + b).is_integer()\n",
    "        \n",
    "        @cache\n",
    "        def dfs(pre: int, state: int) -> int:\n",
    "            if state == u:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            s = set()\n",
    "            for i, x in enumerate(nums):\n",
    "                if state >> i & 1 == 0 and x not in s:\n",
    "                    if pre is None or check(pre, x):\n",
    "                        ans += dfs(x, state | (1 << i))\n",
    "                        s.add(x)\n",
    "            return ans\n",
    "        return dfs(None, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        ln = len(nums)\n",
    "        def check(num1: int, num2: int) -> bool:\n",
    "            sum_ = num1 + num2\n",
    "            return sum_ == (int(sum_ ** 0.5)) ** 2\n",
    "\n",
    "        def backtracking(index: int, prev: int) -> int:\n",
    "            if index == ln:\n",
    "                return 1\n",
    "            current = 0\n",
    "            visited = set()\n",
    "            for i in range(index, ln):\n",
    "                if nums[i] not in visited and (not prev or check(prev, nums[i])):\n",
    "                    visited.add(nums[i])\n",
    "                    nums[index], nums[i] = nums[i], nums[index]\n",
    "                    current += backtracking(index + 1, nums[index])\n",
    "                    nums[index], nums[i] = nums[i], nums[index]\n",
    "\n",
    "            return current\n",
    "        \n",
    "        return backtracking(0, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numSquarefulPerms(self, A):\n",
    "        N = len(A)\n",
    "        count = collections.Counter(A)\n",
    "\n",
    "        graph = {x: [] for x in count}\n",
    "        for x in count:\n",
    "            for y in count:\n",
    "                if int((x+y)**.5 + 0.5) ** 2 == x+y:\n",
    "                    graph[x].append(y)\n",
    "\n",
    "        def dfs(x, todo):\n",
    "            count[x] -= 1\n",
    "            if todo == 0:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for y in graph[x]:\n",
    "                    if count[y]:\n",
    "                        ans += dfs(y, todo - 1)\n",
    "            count[x] += 1\n",
    "            return ans\n",
    "\n",
    "        return sum(dfs(x, len(A) - 1) for x in count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numSquarefulPerms(self, A):\n",
    "        N = len(A)\n",
    "        count = collections.Counter(A)\n",
    "\n",
    "        graph = {x: [] for x in count}\n",
    "        for x in count:\n",
    "            for y in count:\n",
    "                if int((x+y)**.5 + 0.5) ** 2 == x+y:\n",
    "                    graph[x].append(y)\n",
    "\n",
    "        def dfs(x, todo):\n",
    "            count[x] -= 1\n",
    "            if todo == 0:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for y in graph[x]:\n",
    "                    if count[y]:\n",
    "                        ans += dfs(y, todo - 1)\n",
    "            count[x] += 1\n",
    "            return ans\n",
    "\n",
    "        return sum(dfs(x, len(A) - 1) for x in count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numSquarefulPerms(self, A):\n",
    "        N = len(A)\n",
    "        count = collections.Counter(A)\n",
    "\n",
    "        graph = {x: [] for x in count}\n",
    "        for x in count:\n",
    "            for y in count:\n",
    "                if int((x+y)**.5 + 0.5) ** 2 == x+y:\n",
    "                    graph[x].append(y)\n",
    "\n",
    "        def dfs(x, todo):\n",
    "            count[x] -= 1\n",
    "            if todo == 0:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for y in graph[x]:\n",
    "                    if count[y]:\n",
    "                        ans += dfs(y, todo - 1)\n",
    "            count[x] += 1\n",
    "            return ans\n",
    "\n",
    "        return sum(dfs(x, len(A) - 1) for x in count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        # case1: to avoid duplicate,i > 0 and nums[i] == nums[i - 1]\n",
    "        # path: path[-1] + nums[i] = 9 == 3 ** 2, go for backtracking\n",
    "        # [2, 2, 1, 2, 2], [1, 2, 2, 2, 2]\n",
    "        def perfectSquare(n):\n",
    "            return pow(int(sqrt(n)), 2) == n\n",
    "\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                self.res += 1\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if not path or perfectSquare(path[-1] + nums[i]):\n",
    "                    backtrack(nums[:i] + nums[i+1:], path + [nums[i]])\n",
    "        \n",
    "        self.res = 0\n",
    "        backtrack(sorted(nums), [])\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def swap(a, i, j):\n",
    "        a[i], a[j] = a[j], a[i]\n",
    "        \n",
    "    @staticmethod\n",
    "    def getAll(nums, index):\n",
    "        if index == len(nums) - 1:\n",
    "            if int(math.sqrt(nums[index - 1] + nums[index])) ** 2 == nums[index - 1] + nums[index]:\n",
    "                Solution.getAll.s.add(tuple(nums))\n",
    "            return\n",
    "        \n",
    "        for i in range(index, len(nums)):\n",
    "            if i != index and nums[i] == nums[index]:\n",
    "                continue\n",
    "            Solution.swap(nums, i, index)\n",
    "            if index == 0:\n",
    "                Solution.getAll(nums, index + 1)\n",
    "            if index - 1 >= 0 and int(math.sqrt(nums[index - 1] + nums[index])) ** 2 == nums[index - 1] + nums[index]:\n",
    "                Solution.getAll(nums, index + 1)\n",
    "            Solution.swap(nums, i, index)\n",
    "    \n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        Solution.getAll.s = set()\n",
    "        Solution.getAll(nums, 0)\n",
    "        return len(Solution.getAll.s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        ln = len(nums)\n",
    "        def check(num1: int, num2: int) -> bool:\n",
    "            sum_ = num1 + num2\n",
    "            return sum_ == int(sum_ ** 0.5) ** 2\n",
    "\n",
    "        def backtracking(index: int, prev: int) -> int:\n",
    "            if index == ln:\n",
    "                return 1\n",
    "            current = 0\n",
    "            visited = set()\n",
    "            for i in range(index, ln):\n",
    "                if nums[i] not in visited and (not prev or check(prev, nums[i])):\n",
    "                    visited.add(nums[i])\n",
    "                    nums[index], nums[i] = nums[i], nums[index]\n",
    "                    current += backtracking(index + 1, nums[index])\n",
    "                    nums[index], nums[i] = nums[i], nums[index]\n",
    "\n",
    "            return current\n",
    "        \n",
    "        return backtracking(0, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "      count=collections.Counter(nums)\n",
    "      graph={x:[] for x in count}\n",
    "      for x in count:\n",
    "        for y in count:\n",
    "          if int((x+y)**.5 + 0.5) ** 2 == x+y:\n",
    "            graph[x].append(y)\n",
    "\n",
    "      def dfs(x,todo):\n",
    "        if todo==0:\n",
    "\n",
    "          return 1\n",
    "        else:\n",
    "          ans=0\n",
    "          count[x]-=1\n",
    "          for y in graph[x]:\n",
    "            if count[y]!=0:\n",
    "              ans+=dfs(y,todo-1)\n",
    "          count[x]+=1\n",
    "          return ans\n",
    "      key=0\n",
    "      for i in count:\n",
    "        key+=dfs(i,len(nums)-1)\n",
    "      return key          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums):\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        self.res = 0\n",
    "        self.st = [False] * n\n",
    "        self.dfs(0, nums, [])\n",
    "        return self.res\n",
    "\n",
    "    def check(self, x):\n",
    "        t = int(x ** 0.5)\n",
    "        return t * t == x\n",
    "\n",
    "    def dfs(self, u, nums, v):\n",
    "        if u == len(nums):\n",
    "            self.res += 1\n",
    "            return\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if self.st[i] or (i > 0 and nums[i] == nums[i - 1] and self.st[i - 1]):\n",
    "                continue\n",
    "            if v and not self.check(v[-1] + nums[i]):\n",
    "                continue\n",
    "            self.st[i] = True\n",
    "            v.append(nums[i])\n",
    "            self.dfs(u + 1, nums, v)\n",
    "            v.pop()\n",
    "            self.st[i] = False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        count = Counter(nums)\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for i in count:\n",
    "            for j in count:\n",
    "                value = sqrt(i + j)\n",
    "                if int(value) == value:\n",
    "                    graph[i].append(j)\n",
    "                    \n",
    "        def helper(u, i):\n",
    "            if i == n:\n",
    "               return 1 \n",
    "\n",
    "            res = 0 \n",
    "            for v in graph[u]:\n",
    "                if count[v]:\n",
    "                    count[v] -= 1\n",
    "                    res += helper(v, i + 1)\n",
    "                    count[v] += 1\n",
    "                \n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for u in count:\n",
    "            count[u] -= 1\n",
    "            ans += helper(u, 1)\n",
    "            count[u] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def swap(a, i, j):\n",
    "        a[i], a[j] = a[j], a[i]\n",
    "        \n",
    "    @staticmethod\n",
    "    def getAll(nums, index):\n",
    "        if index == len(nums) - 1:\n",
    "            if int(math.sqrt(nums[index - 1] + nums[index])) ** 2 == nums[index - 1] + nums[index]:\n",
    "                Solution.getAll.s.add(tuple(nums))\n",
    "            return\n",
    "        \n",
    "        for i in range(index, len(nums)):\n",
    "            if i != index and nums[i] == nums[index]:\n",
    "                continue\n",
    "            Solution.swap(nums, i, index)\n",
    "            if index == 0:\n",
    "                Solution.getAll(nums, index + 1)\n",
    "            elif int(math.sqrt(nums[index - 1] + nums[index])) ** 2 == nums[index - 1] + nums[index]:\n",
    "                Solution.getAll(nums, index + 1)\n",
    "            Solution.swap(nums, i, index)\n",
    "    \n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        Solution.getAll.s = set()\n",
    "        Solution.getAll(nums, 0)\n",
    "        return len(Solution.getAll.s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    暴力DFS\n",
    "    1.统计数组中每个数出现的次数 num-count\n",
    "    2.笛卡尔积num-count中能够形成加和平方数的组合列表，由于是对num-count做笛卡尔积，相同值的元素只会计算一次，\n",
    "    比如[2, 2, 2]这种，只会有2:2 形成加和平方数组合\n",
    "    3.由于num-count中有所有的节点，所以遍历num-count中的每一个num，表示把num放在第一位，依次找能和num相邻构成\n",
    "    加和平方数的所有可能\n",
    "    由于遍历的是num-count，所以相同数值出现在一个位置上的机会只有一次，从而避免了重复\n",
    "    '''\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        count = Counter(nums)\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for i in count:\n",
    "            for j in count:\n",
    "                value = sqrt(i + j)\n",
    "                if int(value) == value:\n",
    "                    graph[i].append(j)\n",
    "                    \n",
    "        def helper(u, i):\n",
    "            if i == n:\n",
    "               return 1 \n",
    "\n",
    "            res = 0 \n",
    "            for v in graph[u]:\n",
    "                if count[v]:\n",
    "                    count[v] -= 1\n",
    "                    res += helper(v, i + 1)\n",
    "                    count[v] += 1\n",
    "                \n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for u in count:\n",
    "            count[u] -= 1\n",
    "            ans += helper(u, 1)\n",
    "            count[u] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        ln = len(nums)\n",
    "        # 注意，数组中可能有重复元素！！\n",
    "        count = collections.Counter(nums)\n",
    "        graph = collections.defaultdict(list)\n",
    "        graph[None] = list(count.keys())\n",
    "        for x in count:\n",
    "            for y in count:\n",
    "                if int((x + y) ** 0.5) ** 2 == x + y:\n",
    "                    graph[x].append(y)\n",
    "\n",
    "        def backtracking(index: int, prev: int) -> int:\n",
    "            if index == ln:\n",
    "                return 1\n",
    "            result = 0\n",
    "            for num in graph[prev]:\n",
    "                if count[num] > 0:\n",
    "                    count[num] -= 1\n",
    "                    result += backtracking(index + 1, num)\n",
    "                    count[num] += 1\n",
    "            \n",
    "            return result\n",
    "\n",
    "        return backtracking(0, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def swap(a, i, j):\n",
    "        a[i], a[j] = a[j], a[i]\n",
    "        \n",
    "    @staticmethod\n",
    "    def getAll(nums, index):\n",
    "        if index == len(nums) - 1:\n",
    "            if int(math.sqrt(nums[index - 1] + nums[index])) ** 2 == nums[index - 1] + nums[index]:\n",
    "                Solution.getAll.s.add(tuple(nums))\n",
    "            return\n",
    "        \n",
    "        for i in range(index, len(nums)):\n",
    "            if i != index and nums[i] == nums[index]:\n",
    "                continue\n",
    "            Solution.swap(nums, i, index)\n",
    "            if index == 0:\n",
    "                Solution.getAll(nums, index + 1)\n",
    "            if index - 1 >= 0 and int(math.sqrt(nums[index - 1] + nums[index])) ** 2 == nums[index - 1] + nums[index]:\n",
    "                Solution.getAll(nums, index + 1)\n",
    "            Solution.swap(nums, i, index)\n",
    "    \n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        Solution.getAll.s = set()\n",
    "        Solution.getAll(nums, 0)\n",
    "        print(Solution.getAll.s)\n",
    "        return len(Solution.getAll.s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        # case1: to avoid duplicate,i > 0 and nums[i] == nums[i - 1]\n",
    "        # path: path[-1] + nums[i] = 9 == 3 ** 2, go for backtracking\n",
    "        # [2, 2, 1, 2, 2], [1, 2, 2, 2, 2]\n",
    "        def perfectSquare(n):\n",
    "            return pow(int(sqrt(n)), 2) == n\n",
    "\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                self.res += 1\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if not path or perfectSquare(path[-1] + nums[i]):\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(nums[:i] + nums[i+1:], path)\n",
    "                    path.pop()\n",
    "        \n",
    "        self.res = 0\n",
    "        backtrack(sorted(nums), [])\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        def is_perfect_square(n):\n",
    "            return pow(int(sqrt(n)), 2) == n\n",
    "\n",
    "        self.res = 0\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                self.res += 1\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if not path or is_perfect_square(path[-1] + nums[i]):\n",
    "                    backtrack(nums[: i] + nums[i + 1: ], path + [nums[i]])\n",
    "\n",
    "        backtrack(sorted(nums), [])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        nums.sort()\n",
    "\n",
    "        def backtrack(curr, mask):\n",
    "            if len(curr) == len(nums):\n",
    "                print(curr)\n",
    "                self.ans += 1\n",
    "                return\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i-1] and (mask >> (i-1)) & 1 == 0:\n",
    "                    continue # 第 i-1 位没有访问过\n",
    "                if mask | (1 << i) != mask:\n",
    "                    if not curr or int((nums[i] + curr[-1])** 0.5) ** 2 == nums[i] + curr[-1]:\n",
    "                        backtrack(curr+[nums[i]], mask | (1 << i))\n",
    "\n",
    "        backtrack([], 0)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        def is_perfect_square(n):\n",
    "            return pow(int(sqrt(n)), 2) == n\n",
    "\n",
    "        self.res = 0\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                self.res += 1\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if not path or is_perfect_square(path[-1] + nums[i]):\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(nums[: i] + nums[i + 1: ], path)\n",
    "                    path.pop()\n",
    "                    \n",
    "        backtrack(sorted(nums), [])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        usedStat = [False] * n\n",
    "        curNums = []\n",
    "        cnt = 0\n",
    "\n",
    "        def _addNum():\n",
    "            nonlocal n\n",
    "            nonlocal cnt\n",
    "\n",
    "            if len(curNums) == n:\n",
    "                cnt += 1\n",
    "                return\n",
    "            \n",
    "            for idx in range(n):\n",
    "                if usedStat[idx]:\n",
    "                    continue\n",
    "                if idx != 0 and nums[idx - 1] == nums[idx] and not usedStat[idx - 1]:\n",
    "                    continue\n",
    "                if len(curNums) > 0:\n",
    "                    curSum = curNums[-1] + nums[idx]\n",
    "                    curSqrt = math.floor(math.sqrt(curSum))\n",
    "                    if curSqrt ** 2 != curSum:\n",
    "                        continue\n",
    "                usedStat[idx] = True\n",
    "                curNums.append(nums[idx])\n",
    "                _addNum()\n",
    "                usedStat[idx] = False\n",
    "                curNums.pop()\n",
    "\n",
    "        def squareFul(nums):\n",
    "            if len(nums) < 2:\n",
    "                return False\n",
    "\n",
    "            for idx in range(1, len(nums)):\n",
    "                curSum = nums[idx] + nums[idx - 1]\n",
    "                curSqrt = math.floor(math.sqrt(curSum))\n",
    "                if curSqrt ** 2 != curSum:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        _addNum()\n",
    "        return cnt\n",
    "\n",
    "\n",
    "'''\n",
    "generate pernutations\n",
    "usedStat\n",
    "\n",
    "generate(curNums, usedStat):\n",
    "    if len(curNums) == nNums:\n",
    "        if squareful(curNums):\n",
    "            cnt += 1\n",
    "        return\n",
    "    \n",
    "    for idx in nNums:\n",
    "        if used(idx):\n",
    "            continue\n",
    "        if nums[idx - 1] == nums[idx] and not used(idx - 1):\n",
    "            continue\n",
    "        curNums.append(nums[idx])\n",
    "        generate(curNums, usedStat)\n",
    "        curNums.pop()\n",
    "\n",
    "squareful(nums)\n",
    "    for idx in range(1, len(nums)):\n",
    "        curSum = nums[idx - 1] + nums[idx]\n",
    "        curSqrt = math.floor(math.sqrt(curSum))\n",
    "        if curSqrt ** 2 != curSum:\n",
    "            return False\n",
    "    return True\n",
    "    \n",
    "\n",
    "chech if squareful\n",
    "\n",
    "False, False, False\n",
    "\n",
    "1, 1, 2\n",
    "^\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nei = defaultdict(set)\n",
    "        def issqrt(num):\n",
    "            root = int(num ** 0.5)\n",
    "            return num == root ** 2\n",
    "        ex = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if issqrt(nums[i] + nums[j]) and (nums[i], nums[j]) not in ex:\n",
    "                    ex.add((nums[i], nums[j]))\n",
    "                    nei[nums[j]].add(nums[i])\n",
    "                    nei[nums[i]].add(nums[j])\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        def dfs(num, c = 0):\n",
    "            nonlocal ans\n",
    "            c += 1\n",
    "            if c == n:\n",
    "                ans += 1\n",
    "                return \n",
    "            cnt[num] -= 1\n",
    "            for j in nei[num]:\n",
    "                if cnt[j]:\n",
    "                    dfs(j, c)\n",
    "            cnt[num] += 1\n",
    "        for k in cnt.keys():\n",
    "            dfs(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(num):\n",
    "    return (num**0.5)%1==0\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        #状态压缩+记忆化搜索,状态中0表示可以选,1表示已经选过了\n",
    "        n=len(nums)\n",
    "        m=(1<<n)-1\n",
    "        @cache\n",
    "        def dfs(mask,pre):\n",
    "            if mask==m: return 1\n",
    "            res=0\n",
    "            s=set()\n",
    "            for i in range(n):\n",
    "                if mask>>i&1==0 and nums[i] not in s and (pre==-1 or check(nums[pre]+nums[i])):\n",
    "                    #可选\n",
    "                    res+=dfs(mask^(1<<i),i)\n",
    "                    s.add(nums[i])\n",
    "            return res\n",
    "        return dfs(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        g = defaultdict(list)\n",
    "        for x in cnt:\n",
    "            for y in cnt:\n",
    "                if int((x+y)**.5 + 0.5) ** 2 == x + y: \n",
    "                    g[x].append(y)\n",
    "        \n",
    "        def dfs(x, todo):\n",
    "            cnt[x] -= 1\n",
    "            if not todo:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for y in g[x]:\n",
    "                    if cnt[y]:\n",
    "                        ans += dfs(y, todo - 1)\n",
    "            cnt[x] += 1\n",
    "            return ans\n",
    "        return sum(dfs(x, n - 1) for x in cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        def judge(x):\n",
    "            return int(x**0.5)**2 == x\n",
    "        \n",
    "        def traverse(nums, path):\n",
    "            if not nums:\n",
    "                res.append(path[:]) \n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i-1]:\n",
    "                    continue \n",
    "                if not path or judge(path[-1]+nums[i]):\n",
    "                    traverse(nums[:i]+nums[i+1:], path+[nums[i]])\n",
    "        \n",
    "        nums.sort()\n",
    "        res = []\n",
    "        traverse(nums, [])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        def is_square(x):\n",
    "            sq = int(sqrt(x))\n",
    "            return x ==  sq * sq\n",
    "        n = len(nums)\n",
    "        vis = [False] * n\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        def dfs(i, cur):\n",
    "            nonlocal ans\n",
    "            if len(cur) == n:\n",
    "                # print(f'{cur}')\n",
    "                ans += 1\n",
    "            for j in range(n):\n",
    "                if i != -1 and j > 0 and nums[j - 1] == nums[j] and not vis[j - 1]: continue\n",
    "                if i == -1 and j > 0 and nums[j] == nums[j - 1]: continue\n",
    "                if i == -1 or (not vis[j] and is_square(nums[i] + nums[j])):\n",
    "                    vis[j] = True\n",
    "                    cur.append(j)\n",
    "                    dfs(j, cur)\n",
    "                    cur.pop()\n",
    "                    vis[j] = False\n",
    "        # for i in range(1, 10):\n",
    "        #     print(f'{i}: {is_square(i)}')\n",
    "        dfs(-1, [])\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        self.res = []\n",
    "        self.dfs(nums, [])\n",
    "        return len(self.res)\n",
    "                    \n",
    "    def dfs(self, nums, path):\n",
    "        if not nums:\n",
    "            self.res.append(path)\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            if not path or self.valid(path[-1] + nums[i]):\n",
    "                self.dfs(nums[:i] + nums[i+1:], path + [nums[i]])\n",
    "                \n",
    "    def valid(self, a):\n",
    "        if int(a**0.5)**2 == a:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        u = (1 << n) - 1\n",
    "        def check(a: int, b: int) -> bool:\n",
    "            return sqrt(a + b).is_integer()\n",
    "        \n",
    "        # @cache\n",
    "        def dfs(pre: int, state: int) -> int:\n",
    "            if state == u:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            s = set()\n",
    "            for i, x in enumerate(nums):\n",
    "                if state >> i & 1 == 0 and x not in s:\n",
    "                    if pre is None or check(pre, x):\n",
    "                        ans += dfs(x, state | (1 << i))\n",
    "                        s.add(x)\n",
    "            return ans\n",
    "        return dfs(None, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def square_num(a:int,b:int)->bool:\n",
    "            if int(sqrt(a+b)) ** 2 != a+b:\n",
    "                return False\n",
    "            return True\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        # 状态为1表示未被选择\n",
    "        # dfs的含义是在当前选择了cur这个数的前提下，f中标志为1的还未被选择，\n",
    "        # 返回当前状态下正方形数组的个数\n",
    "        # 好像不需要记忆化也能过\n",
    "        def dfs(cur: int, f : int)->int:\n",
    "            if f == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                # nums[i]和cur的和可构成完全平方数，那么nums[i]才有资格作为cur的下一个数\n",
    "                if (1 << i) & f and square_num(cur, nums[i]):\n",
    "                    # nums[i]==nums[i-1]并且nums[i-1]也没有被选择，需要去重，直接省略即可\n",
    "                    if i > 0 and (1 << (i-1)) & f and nums[i-1] == nums[i]:\n",
    "                        continue\n",
    "                    res += dfs(nums[i],(1 << i) ^ f)\n",
    "            return res\n",
    "        f = (1 << n) - 1\n",
    "        for i in range(n):\n",
    "            # 同理，需要去重\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            ans += dfs(nums[i], (1<<i) ^ f)\n",
    "        return ans\n",
    " \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        def is_perfect_square(n):\n",
    "            return pow(int(sqrt(n)), 2) == n\n",
    "\n",
    "        self.res = 0\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                self.res += 1\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if not path or is_perfect_square(path[-1] + nums[i]):\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(nums[: i] + nums[i + 1: ], path)\n",
    "                    path.pop()\n",
    "                    \n",
    "        backtrack(sorted(nums), [])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def square_num(a:int,b:int)->bool:\n",
    "            if int(sqrt(a+b)) ** 2 != a+b:\n",
    "                return False\n",
    "            return True\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        def dfs(cur: int, f : int)->int:\n",
    "            if f == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (1 << i) & f and square_num(cur, nums[i]):\n",
    "                    if i > 0 and (1 << (i-1)) & f and nums[i-1] == nums[i]:\n",
    "                        continue\n",
    "                    res += dfs(nums[i],(1 << i) ^ f)\n",
    "            return res\n",
    "        f = (1 << n) - 1\n",
    "        for i in range(n):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            ans += dfs(nums[i], (1<<i) ^ f)\n",
    "        return ans\n",
    " \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        info = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                tmp = sqrt(nums[i] + nums[j])\n",
    "                tmp = int(tmp)\n",
    "                if tmp * tmp == nums[i] + nums[j]:\n",
    "                    if info.get(i, None) is None:\n",
    "                        info[i] = []\n",
    "                    if info.get(j, None) is None:\n",
    "                        info[j] = []\n",
    "                    \n",
    "                    info[i].append(j)\n",
    "                    info[j].append(i)\n",
    "        \n",
    "\n",
    "        if len(info) < len(nums):\n",
    "            return 0\n",
    "        \n",
    "        visited = set()\n",
    "        visited2 = set()\n",
    "        comp = []\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in visited2:\n",
    "                continue\n",
    "            visited.add(i)\n",
    "            visited2.add(nums[i])\n",
    "            comp.append(i)\n",
    "            # for j in info[i]:\n",
    "            #     visited.add(j)\n",
    "            #     comp.append(j)\n",
    "            #     res += self.recurse(nums, info, comp, visited)\n",
    "            #     visited.remove(j)\n",
    "            #     comp.pop()\n",
    "            res += self.recurse(nums, info, comp, visited)\n",
    "            visited.remove(i)\n",
    "            comp.pop()\n",
    "\n",
    "        # self.recurse(nums, info, comp, visited)\n",
    "        return res\n",
    "    \n",
    "    def recurse(self, nums, info, comp, visited):\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     if i in visited:\n",
    "        #         continue\n",
    "        #     visited.add(i)\n",
    "\n",
    "        if len(comp) == len(nums):\n",
    "            return 1\n",
    "        \n",
    "        res = 0\n",
    "        visited2 = set()\n",
    "        for i in info.get(comp[-1], ()):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            if nums[i] in visited2:\n",
    "                continue\n",
    "            visited.add(i)\n",
    "            visited2.add(nums[i])\n",
    "            comp.append(i)\n",
    "            res += self.recurse(nums, info, comp, visited)\n",
    "            visited.remove(i)\n",
    "            comp.pop()\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        # nums.sort()\r\n",
    "\r\n",
    "        ans = 0\r\n",
    "        def backtrack(index, pre=-1):\r\n",
    "            if index == n:\r\n",
    "                nonlocal ans\r\n",
    "                ans += 1\r\n",
    "                return\r\n",
    "            visited = set()\r\n",
    "            for i in range(index, n):\r\n",
    "                if nums[i] not in visited and (pre < 0 or int(math.sqrt(pre + nums[i])) ** 2 == pre + nums[i]):\r\n",
    "                    nums[i], nums[index] = nums[index], nums[i]\r\n",
    "                    # print(index, nums)\r\n",
    "                    backtrack(index + 1, nums[index])\r\n",
    "                    nums[i], nums[index] = nums[index], nums[i]\r\n",
    "                    visited.add(nums[i])\r\n",
    "        \r\n",
    "        backtrack(0)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        def is_square(x):\n",
    "            return int(math.sqrt(x)) ** 2 == x\n",
    "        res = 0\n",
    "\n",
    "        candidates = set()\n",
    "\n",
    "        # # 从答案角度出发，选择选哪个\n",
    "        # def dfs(i,last,used,path):\n",
    "        #     nonlocal res\n",
    "        #     # [i:] 寻找其排列使得从i开始往后为squareful 假设i应与上一个squareful （为了方便检查上一个，path设第一个dummy zero）\n",
    "        #     if i == n:\n",
    "        #         if path not in candidates:\n",
    "        #             candidates.add(path)\n",
    "        #             res += 1\n",
    "        #         return\n",
    "\n",
    "        #     for j in range(n):\n",
    "        #         if used >> j & 1 == 0 and is_square(last + nums[j]):\n",
    "        #             dfs(i+1, nums[j], used | (1<<j),path+str(nums[j]))\n",
    "                    \n",
    "        # # dfs(0,0,0) 不适合 222 (0+2 not squareful)\n",
    "        # # 222 还有去重问题，如何提前截断？\n",
    "        # for i in range(n):\n",
    "        #     dfs(1, nums[i], 1 << i, str(nums[i]))\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # 从答案角度出发，选择选哪个\n",
    "        def dfs(i,last,used,path):\n",
    "            nonlocal res\n",
    "            # [i:] 寻找其排列使得从i开始往后为squareful 假设i应与上一个squareful （为了方便检查上一个，path设第一个dummy zero）\n",
    "            # print(i, path)\n",
    "            if i == n:\n",
    "                # if path not in candidates:\n",
    "                #     candidates.add(path)\n",
    "                res += 1\n",
    "                return\n",
    "\n",
    "            for j in range(n):\n",
    "                if used >> j & 1 == 0 and is_square(last + nums[j]):\n",
    "                    # print(\"-\", last, j, is_square(last + nums[j]))\n",
    "                    path1 = path+str(nums[j])\n",
    "                    if path1 not in candidates:\n",
    "                        candidates.add(path1)\n",
    "                        dfs(i+1, nums[j], used | (1<<j),path1)\n",
    "                    \n",
    "        # dfs(0,0,0) 不适合 222 (0+2 not squareful)\n",
    "        # 222 还有去重问题，如何提前截断？\n",
    "        for i in range(n):\n",
    "            dfs(1, nums[i], 1 << i, str(nums[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def square_num(a:int,b:int)->bool:\n",
    "            if int(sqrt(a+b)) ** 2 != a+b:\n",
    "                return False\n",
    "            return True\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur: int, f : int)->int:\n",
    "            if f == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (1 << i) & f and square_num(cur, nums[i]):\n",
    "                    if i > 0 and (1 << (i-1)) & f and nums[i-1] == nums[i]:\n",
    "                        continue\n",
    "                    res += dfs(nums[i],(1 << i) ^ f)\n",
    "            return res\n",
    "        f = (1 << n) - 1\n",
    "        for i in range(n):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            ans += dfs(nums[i], (1<<i) ^ f)\n",
    "        return ans\n",
    " \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        # case1: to avoid duplicate,i > 0 and nums[i] == nums[i - 1]\n",
    "        # path: path[-1] + nums[i] = 9 == 3 ** 2, go for backtracking\n",
    "        # [2, 2, 1, 2, 2], [1, 2, 2, 2, 2]\n",
    "        def perfectSquare(n):\n",
    "            return pow(int(sqrt(n)), 2) == n\n",
    "\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                self.res += 1\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if not path or perfectSquare(path[-1] + nums[i]):\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(nums[:i] + nums[i+1:], path)\n",
    "                    path.pop()\n",
    "        \n",
    "        self.res = 0\n",
    "        backtrack(sorted(nums), [])\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        count = Counter(nums)\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for i in count:\n",
    "            for j in count:\n",
    "                v = sqrt(i + j)\n",
    "                if int(v) == v:\n",
    "                    graph[i].append(j)\n",
    "        \n",
    "        def helper(u, i):\n",
    "            if i == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0 \n",
    "            for v in graph[u]:\n",
    "                if count[v]:\n",
    "                    count[v] -= 1\n",
    "                    res += helper(v, i + 1)\n",
    "                    count[v] += 1\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for u in count:\n",
    "            count[u] -= 1\n",
    "            ans += helper(u, 1)\n",
    "            count[u] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "\n",
    "        dp=[[0]*n for _ in range(1<<n)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def funsqrt(i,j):\n",
    "            sums=nums[i]+nums[j]\n",
    "            return int(sums**0.5)**2==sums\n",
    "\n",
    "        for i in range(1,1<<n):\n",
    "            for j in range(n):\n",
    "                if i&(1<<j):\n",
    "                    dpstate=i^(1<<j)\n",
    "                    if dpstate==0:\n",
    "                        dp[i][j]+=1\n",
    "                    else:\n",
    "                        for k in range(n):\n",
    "                            if dpstate & (1<<k) and funsqrt(k,j):\n",
    "                                dp[i][j]+=dp[dpstate][k]\n",
    "\n",
    "        counter=Counter(nums)\n",
    "        repeat=1\n",
    "        for k, v in counter.items():\n",
    "            while(v):\n",
    "                repeat *= v\n",
    "                v -= 1\n",
    "        return sum(dp[-1][i] for i in range(n)) // repeat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums) -> int:\n",
    "        n = len(nums)\n",
    "        repeat = Counter(nums)\n",
    "        mem = {i:[-1] * 2**n for i in repeat}\n",
    "        graph = {i: [] for i in range(n)}\n",
    "        res = 0\n",
    "        def checker(a, b):\n",
    "            s = a+b\n",
    "            return int(s ** 0.5) ** 2 == s\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                elif checker(nums[i], nums[j]):\n",
    "                    graph[i].append(j)\n",
    "\n",
    "        def dfs(index, visited, depth = 0):\n",
    "            nonlocal graph, mem\n",
    "            if visited == 2 ** n - 1:\n",
    "                return 1\n",
    "\n",
    "            if nums[index] in mem:\n",
    "                a = mem[nums[index]][visited]\n",
    "                if a != -1:\n",
    "                    return a\n",
    "            res = 0\n",
    "            for c in graph[index]:\n",
    "                if not visited & (1 << c):\n",
    "                    res += dfs(c, visited ^ (1 << c), depth + 2)\n",
    "            if visited not in mem[nums[index]]:\n",
    "                mem[nums[index]][visited] = res\n",
    "            \n",
    "            return res\n",
    "\n",
    "        def fact(n):\n",
    "            res = 1\n",
    "            for i in range(2, n+1):\n",
    "                res *= i\n",
    "            return res\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            res += dfs(i, 1 << i)\n",
    "\n",
    "        for i in repeat:\n",
    "            res /= fact(repeat[i])\n",
    "        return int(res)\n",
    "\n",
    "     \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def fun(now, last, mask):\n",
    "            if now == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if not mask & (1 << i) and sqrt(last+nums[i]).is_integer():\n",
    "                    res += fun(now+1, nums[i], mask | (1 << i))\n",
    "            return res\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += fun(1, nums[i], 1 << i)\n",
    "        f = 1\n",
    "        for v in Counter(nums).values():\n",
    "            f *= factorial(v)\n",
    "        return res // f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        def edge(x, y):\n",
    "            r = math.sqrt(x+y)\n",
    "            return int(r + 0.5) ** 2 == x+y\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                if edge(x, nums[j]):\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "\n",
    "        # dfs(node, visited) 等于从 node 节点出发访问剩余的节点的可行方法数。\n",
    "        @lru_cache(None)\n",
    "        def dfs(node, visited):\n",
    "            if visited == (1 << n) - 1:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "            for nei in graph[node]:\n",
    "                if (visited >> nei) & 1 == 0:\n",
    "                    ans += dfs(nei, visited | (1 << nei))\n",
    "            return ans\n",
    "\n",
    "        ans = sum(dfs(i, 1<<i) for i in range(n))\n",
    "        count = collections.Counter(nums)\n",
    "        for v in count.values():\n",
    "            ans //= math.factorial(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        mask = (1 << n) - 1\n",
    "\n",
    "        def is_sqrt(x):\n",
    "            t = int(sqrt(x))\n",
    "            if t * t == x:\n",
    "                return True\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(mask,pre_index):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i,x in enumerate(nums):\n",
    "                if (mask >> i) & 1:\n",
    "                    if pre_index == -1 or is_sqrt(x + nums[pre_index]):\n",
    "                        ans += dfs(mask ^(1 << i),i)\n",
    "            return ans\n",
    "        \n",
    "        t = dfs(mask,-1)\n",
    "        for k,v in Counter(nums).items():\n",
    "            t //= factorial(v)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                x = nums[i]+nums[j]\n",
    "                y = int(x**0.5)\n",
    "                if y*y == x:\n",
    "                    dct[i].append(j)\n",
    "                    dct[j].append(i)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(a, state):\n",
    "            if not state:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for b in dct[a]:\n",
    "                if state & (1<<b):\n",
    "                    res += dfs(b, state^(1<<b))\n",
    "            return res\n",
    "        \n",
    "        ans = sum(dfs(i, ((1<<n)-1)^(1<<i)) for i in range(n))\n",
    "        cnt = Counter(nums)\n",
    "        for num in cnt:\n",
    "            c = cnt[num]\n",
    "            if c > 1:\n",
    "                ans //= math.factorial(c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        num2num = dict()\n",
    "        \n",
    "        for each in nums:\n",
    "            if each in num2num:\n",
    "                num2num[each] += 1\n",
    "            else:\n",
    "                num2num[each] = 1\n",
    "\n",
    "        divided = 1\n",
    "        for k, v in num2num.items():\n",
    "            divided *= math.factorial(v)\n",
    "\n",
    "        graph = [[] for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                sums = nums[i] + nums[j]\n",
    "                if int(sqrt(sums) + 0.5) ** 2 == sums:\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, visit) -> int:\n",
    "            if visit == (1 << (len(nums))) - 1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for each in graph[cur]:\n",
    "                if (visit >> each) & 1 == 0:\n",
    "                    ans += dfs(each, visit | (1 << each)) \n",
    "            return ans\n",
    "        \n",
    "        ans = sum(dfs(i, 1 << i) for i in range(len(nums)))\n",
    "        ans /= divided\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "#     def numSquarefulPerms(self, nums) -> int:\n",
    "#         n = len(nums)\n",
    "#         repeat = Counter(nums)\n",
    "#         mem = {i:[-1] * 2**n for i in repeat}\n",
    "#         graph = {i: [] for i in range(n)}\n",
    "#         res = 0\n",
    "#         def checker(a, b):\n",
    "#             s = a+b\n",
    "#             return int(s ** 0.5) ** 2 == s\n",
    "\n",
    "#         for i in range(n):\n",
    "#             for j in range(n):\n",
    "#                 if i == j:\n",
    "#                     continue\n",
    "#                 elif checker(nums[i], nums[j]):\n",
    "#                     graph[i].append(j)\n",
    "\n",
    "#         def dfs(index, visited, depth = 0):\n",
    "#             nonlocal graph, mem\n",
    "#             if visited == 2 ** n - 1:\n",
    "#                 return 1\n",
    "\n",
    "#             if nums[index] in mem:\n",
    "#                 a = mem[nums[index]][visited]\n",
    "#                 if a != -1:\n",
    "#                     return a\n",
    "#             res = 0\n",
    "#             for c in graph[index]:\n",
    "#                 if not visited & (1 << c):\n",
    "#                     res += dfs(c, visited ^ (1 << c), depth + 2)\n",
    "#             if visited not in mem[nums[index]]:\n",
    "#                 mem[nums[index]][visited] = res\n",
    "            \n",
    "#             return res\n",
    "\n",
    "#         def fact(n):\n",
    "#             res = 1\n",
    "#             for i in range(2, n+1):\n",
    "#                 res *= i\n",
    "#             return res\n",
    "\n",
    "\n",
    "#         for i in range(n):\n",
    "#             res += dfs(i, 1 << i)\n",
    "\n",
    "#         for i in repeat:\n",
    "#             res /= fact(repeat[i])\n",
    "#         return int(res)\n",
    "  def numSquarefulPerms(self, A):\n",
    "        N = len(A)\n",
    "\n",
    "        def edge(x, y):\n",
    "            r = math.sqrt(x+y)\n",
    "            return int(r + 0.5) ** 2 == x+y\n",
    "\n",
    "        graph = [[] for _ in range(len(A))]\n",
    "        for i, x in enumerate(A):\n",
    "            for j in range(i):\n",
    "                if edge(x, A[j]):\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "\n",
    "        # find num of hamiltonian paths in graph\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(node, visited):\n",
    "            if visited == (1 << N) - 1:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "            for nei in graph[node]:\n",
    "                if (visited >> nei) & 1 == 0:\n",
    "                    ans += dfs(nei, visited | (1 << nei))\n",
    "            return ans\n",
    "\n",
    "        ans = sum(dfs(i, 1<<i) for i in range(N))\n",
    "        count = collections.Counter(A)\n",
    "        for v in count.values():\n",
    "            ans //= math.factorial(v)\n",
    "        return ans\n",
    "\n",
    "\n",
    "     \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        mask = (1 << n) - 1\n",
    "\n",
    "        def is_sqrt(x):\n",
    "            t = int(sqrt(x))\n",
    "            if t * t == x:\n",
    "                return True\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(mask,pre_index):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i,x in enumerate(nums):\n",
    "                if (mask >> i) & 1:\n",
    "                    if pre_index == -1 or is_sqrt(x + nums[pre_index]):\n",
    "                        ans += dfs(mask ^(1 << i),i)\n",
    "            return ans\n",
    "        \n",
    "        t = dfs(mask,-1)\n",
    "        print(t)\n",
    "        for k,v in Counter(nums).items():\n",
    "            t //= factorial(v)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                v = sqrt(nums[i] + nums[j])\n",
    "                if int(v) == v:\n",
    "                    graph[i].append(j)\n",
    "\n",
    "        mask = (1 << n) - 1\n",
    "        @cache\n",
    "        def helper(u, cur):\n",
    "            if cur == mask:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for v in graph[u]:\n",
    "                if (1 << v) & cur:\n",
    "                    continue\n",
    "                res += helper(v, cur | (1 << v)) \n",
    "            return res\n",
    "        \n",
    "        ans = sum(helper(i, 1 << i) for i in range(n))\n",
    "        count = Counter(nums)\n",
    "        for u in count:\n",
    "            ans //= math.factorial(count[u])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    状压DP\n",
    "    状态压缩的是数组nums中的每一个元素是否被选择过的状态\n",
    "    但是用这种状压的话怎么过滤掉重复元素呢？又出现组合数学了\n",
    "    假设在n个元素中选择k个元素，且n中元素各不相同，那么组合公式为C(n, k) = n! // k! * (n - k)!，\n",
    "    举个例子求C(5,2) = 5 * 4 * 3 * 2 // 2 * (3 * 2) = 5 * 4 // 2 = 10\n",
    "    如果k中有p个相同的元素，那么在p中任选元素的概率为p!，那么排除掉重复元素后的组合数为C(n, k) // p!\n",
    "    所以本题我们在求nums中满足条件的组合数时，可以先假设nums中都是不同的元素，求出总的组合数，然后再\n",
    "    除以重复元素的阶乘，这样就可以在计算组合数的时候使用状压了\n",
    "    '''\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        '''\n",
    "        求出nums中满足与nums[i]元素相加和是完全平方数的所有组合，其中不包含自身，但包含重复的元素\n",
    "        由于状压压的是下标，不是对应的元素值，所以graph中只存储下标\n",
    "        '''\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                v = sqrt(nums[i] + nums[j])\n",
    "                if int(v) == v:\n",
    "                    graph[i].append(j)\n",
    "\n",
    "        mask = (1 << n) - 1\n",
    "        @cache\n",
    "        def helper(u, cur):\n",
    "            if cur == mask:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for v in graph[u]:\n",
    "                if (1 << v) & cur:\n",
    "                    continue\n",
    "                res += helper(v, cur | (1 << v)) \n",
    "            return res\n",
    "        ''' \n",
    "        求出包含重复元素的满足题目要求的组合数之和\n",
    "        这里i是从0开始，状压形成的二进制数是从右到左，而数组是从左到右，\n",
    "        但是没有关系，由于是完全对称的，可以直接按反着来\n",
    "        ''' \n",
    "        ans = sum(helper(i, 1 << i) for i in range(n))\n",
    "        count = Counter(nums)\n",
    "        for u in count:\n",
    "            ans //= math.factorial(count[u])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSquarefulPerms(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                v = sqrt(nums[i] + nums[j])\n",
    "                if int(v) == v:\n",
    "                    graph[i].append(j)\n",
    "\n",
    "        mask = (1 << n) - 1\n",
    "        @cache\n",
    "        def helper(u, cur):\n",
    "            if cur == mask:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for v in graph[u]:\n",
    "                if (1 << v) & cur:\n",
    "                    continue\n",
    "                res += helper(v, cur | (1 << v)) \n",
    "            return res\n",
    "        \n",
    "        ans = sum(helper(i, 1 << i) for i in range(n))\n",
    "        count = Counter(nums)\n",
    "        for u in count:\n",
    "            ans //= math.factorial(count[u])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
